package com.ljy.my_study.lintcode.动态规划.背包问题;
/** 
* @author James
* @date 2019年5月11日 
*/
public class TestMain {
//	在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]
//
//	你不可以将物品进行切割。
//
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	样例 1:
//		输入:  [3,4,8,5], backpack size=10
//		输出:  9
//
//	样例 2:
//		输入:  [2,3,5,7], backpack size=12
//		输出:  12
//		
//	挑战
//	O(n x m) time and O(m) memory.
//
//	O(n x m) memory is also acceptable if you do not know how to optimize memory.
	public static void main(String[] args) {
		
	}
	
	public int backPack(int m, int[] A) {
		int n=A.length;
		if(n==0) {
			return 0;
		}
		int[][] sum=new int[n+1][m+1];
		for(int i=1;i<=m;i++) {
			if(A[0]<=i) {
				sum[1][i]=A[0];
			}
		}
		for(int i=2;i<=n;i++) {
			for(int j=1;j<=m;j++) {
				if(A[i-1]+sum[i-1][j]<=j) {
					sum[i][j]=A[i-1]+sum[i-1][j];
				}else {
//					sum[i][j]=
				}
			}
		}
		return -1;
	}
}
